/**
 * 207. 课程表
 * https://leetcode-cn.com/problems/course-schedule/
 */

/**
 * @constructor
 */
function Course() {
  this.deps = [];
}

/**
 * @param {number} index
 * @param {Course[]} courses
 * @param {boolean[]} children
 * @param {boolean[]} cache
 * @return {boolean}
 */
function canFinishCourseAt(index, courses, children, cache) {
  const { deps } = courses[index];
  if (!deps.length) {
    return true;
  }
  if (cache[index] !== undefined) {
    return cache[index];
  }
  if (children[index]) {
    return false;
  }
  let flag = true;
  children[index] = true;
  for (let i = 0; i < deps.length; i += 1) {
    if (!canFinishCourseAt(deps[i], courses, children, cache)) {
      flag = false;
      break;
    }
  }
  children[index] = false;
  if (flag) {
    cache[index] = true;
    return true;
  }
  cache[index] = false;
  return false;
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
function canFinish(numCourses, prerequisites) {
  const courses = new Array(numCourses);
  for (let i = 0; i < numCourses; i += 1) {
    courses[i] = new Course();
  }
  for (let i = 0; i < prerequisites.length; i += 1) {
    const [target, dep] = prerequisites[i];
    courses[target].deps.push(dep);
  }
  const signatures = new Array(numCourses).fill(false);
  const cache = new Array(numCourses);
  for (let i = 0; i < courses.length; i += 1) {
    if (!canFinishCourseAt(i, courses, signatures, cache)) {
      return false;
    }
  }
  return true;
}

console.log(canFinish(2, [[1, 0]]) === true);
console.log(canFinish(2, [[1, 0], [0, 1]]) === false);
